package 题目集.线段树or树状数组.树状数组;

import java.util.Arrays;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/longest-increasing-subsequence/description/
 *获取左侧比它小的长度最大值，单点修改和区间查询最大值。
 *只涉及到左侧的最大值，并且长度这个值只会增不会减，所以可以用树状数组维护
 */
public class demo01_最长上升子序列 {
	int[] tree;

	public int lengthOfLIS(int[] nums) {
		boolean[] vis = new boolean[nums.length + 1]; // 离散化下标从1开始
		tree = new int[nums.length + 1];
		agge(nums);
		int ans = 0;
		for (int i = 0; i < nums.length; i++) {
			int cur = query(nums[i] - 1) + 1;
			ans = Math.max(ans, cur);
			add(nums[i],cur);
		}
		return ans;
	}

	public void add(int i, int v) {
		for (; i < tree.length; i += i & -i)
			tree[i] = Math.max(tree[i], v);
	}

	public int query(int i) {
		int ans = 0;
		for (; i > 0; i -= i & -i) {
			ans = Math.max(tree[i], ans);
		}
		return ans;
	}

	public void agge(int[] arr) {
		int[] sort = arr.clone();
		Arrays.sort(sort);
		for (int i = 0; i < arr.length; i++) {
			arr[i] = rank(sort, arr[i]);
		}
	}

	public int rank(int[] sort, int v) {
		int l = 0, r = sort.length - 1;
		while (l <= r) {
			int m = l + r >> 1;
			if (sort[m] < v) {
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return l + 1;
	}
	@Test
	public void test() {
		int[] arr= {10,9,2,5,3,7,101,18};
		int len=lengthOfLIS(arr);
		System.out.println(len);
	}
}
